package com.mikelouis.test.scala.proginscala.chapter16

/**
 * Created by yuazhu on 1/19/2015.
 */
object MergeSort {

  /**
   * merge sort
   * @param less
   * @param xs
   * @tparam T
   * @return
   */
  def msort[T](less: (T, T) => Boolean)
              (xs: List[T]): List[T] = {

    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if (less(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(msort(less)(ys), msort(less)(zs))
    }
  }

  /**
   * 两个操作都是列表  (右结合)
   * @return
   */
  def assoc = {
    val xs = List("x")
    val ys = List("y")
    val zs = List("z")
    val l1 =
      xs ::: ys ::: zs
    val l2 =
      xs ::: (ys ::: zs)
    l1 == l2
  }

  def forList = {
    for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)
  }

  def main(args: Array[String]) {
    println("assoc [" + assoc + "]")
    println("msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)) [" +
      msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)) +
      "]")

    println("forList [" + forList + "]")

    /** next suite of test */
    println(msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)))
    val intSort = msort((x: Int, y: Int) => x < y) _
    val reverseIntSort = msort((x: Int, y: Int) => x > y) _

    val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)
    println(intSort(mixedInts))
    println(reverseIntSort(mixedInts))


  }
}
